#include <bits/stdc++.h>

using namespace std;

// 二维数组上单点增加、范围查询，使用树状数组的模版
// 测试链接 : https://leetcode.cn/problems/range-sum-query-2d-mutable/
class NumMatrix
{
public:
    int n, m;
    vector<vector<int>> tree;
    vector<vector<int>> nums;

    int lowbit(int i)
    {
        return x & -i;
    }

    void add(int x, int y, int v)
    {
        for(int i = x; i <= n; i += lowbit(i))
        {
            for(int j = y; j <= m; j += lowbit(j))
            {
                tree[i][j] += v;
            }
        }
    }

    // 从(1,1)到(x,y)这个部分的累加和
    int sum(int x, int y)
    {
        int ans = 0;
        for(int i = x; i > 0; i -= lowbit(i))
        {
            for(int j = y; j > 0; j -= lowbit(j))
            {
                ans += tree[i][j];
            }
        }
        return ans;
    }

    // 实际二维数组的位置是(x,y)
    // 树状数组上的位置是(x+1, y+1)
    // 题目说的是单点更新，转化成单点增加(老值-新值)即可
    // 不要忘了在nums中把老值改成新值
    void update(int x, int y, int v)
    {
        add(x + 1, y + 1, v - nums[x + 1][y + 1]);
        nums[x + 1][y + 1] = v;
    }

    // 实际二维数组的位置是(x,y)
    // 树状数组上的位置是(x+1, y+1)
    int sumRegion(int a, int b, int c, int d)
    {
        return sum(c + 1, d + 1) - sum(a, d + 1) - sum(c + 1, b) + sum(a, b);
    }

    // 入参二维数组下标从0开始
    // 树状数组一定下标从1开始
    NumMatrix(vector<vector<int>>& matrix)
    {
        n = matrix.size();
        m = matrix[0].size();
        tree = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        nums = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                update(i, j, matrix[i][j]);
            }
        }
    }
};